package com.lmk.dsa.algorithm.graph.shortestPath;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import com.lmk.dsa.struct.commons.Edge;
import com.lmk.dsa.struct.graph.Graph;
import com.lmk.dsa.struct.heap.MinIndexHeap;

/**
 * 迪杰斯特拉算法（Dijkstra） 单源最短路径算法，不支持负权边
 * @author LaoMake
 * @since 1.0
 */
public class Dijkstra {

    /** 图 */
    private Graph graph;

    /** 顶点的总数 */
    private int n;

    /** 起始节点索引 */
    private int source;

    /** 从起始节点到目标节点的最小权值数组 */
    private int[] distTo;

    /** 节点访问状态数组 */
    private boolean[] marked;

    /** 标记索引位置的节点通过哪条边到达 */
    private Edge[] from;

    /** 最小索引堆 */
    private MinIndexHeap indexHeap;

    public Dijkstra(Graph graph, int source) {
        this.source = source;
        this.graph = graph;
        n = graph.vertexSize();
        distTo = new int[n];
        marked = new boolean[n];
        from = new Edge[n];
        indexHeap = new MinIndexHeap(n);
        shortestPath();
    }

    /**
     * 求取最短路径
     */
    private void shortestPath(){
        assert source >=0 && source < n;

        distTo[source] = 0;      // 源点到自己路径为0
        marked[source] = true;   // 源点标记为已访问
        indexHeap.insert(source, distTo[source]); // 源点入堆

        while (indexHeap.size() > 0){
            // 取出最短边
            int v =  indexHeap.poolIndex();
            marked[v] = true;

            // 取出所有邻边
            List<Edge> adjEdgeList = graph.adjoinEdge(v);
            int w;
            for (Edge edge : adjEdgeList){
                w = edge.other(v); // 获取边的另一节点索引
                if(!marked[w]){
                    // 如果不存在已有路径，或者新的中转路径比先前路径还短，则进行松弛操作
                    if (from[w] == null || distTo[v] + edge.weight < distTo[w]){
                        distTo[w] = distTo[v] + edge.weight;
                        from[w] = edge;

                        if(indexHeap.containsIndex(w)){
                            // 如果该节点已存在堆中，则更新他的值
                            indexHeap.change(w, distTo[w]);
                        }else{
                            // 如果该节点不在堆中，则入堆
                            indexHeap.insert(w, distTo[w]);
                        }
                    }
                }
            }
        }
    }

    /**
     * 判断是否可以到达目标节点
     * @param to
     * @return
     */
    public boolean hasPathTo(int to){
        assert to >=0 && to < n;
        return marked[to];
    }

    /**
     * 获取到指定节点的最短路径值
     * @param to
     * @return
     */
    public int shortestPathTo(int to){
        assert to >=0 && to < n;
        return distTo[to];
    }

    /**
     * 获取到达指定节点的最短路径（边）
     * @param to
     * @return
     */
    public List<Edge> shortestPath(int to){
        // 查询完整路径
        Stack<Edge> stack = new Stack<>();
        Edge edge = from[to];
        while (edge != null && edge.from != edge.to){
            stack.push(edge);
            edge = from[edge.from];
        }

        // 依次将栈内边取回
        List<Edge> edgeList = new ArrayList<>(stack.size());
        while (!stack.isEmpty()){
            edgeList.add(stack.pop());
        }

        return edgeList;
    }


    /**
     * 打印到指定节点的最短路径
     * @param to
     */
    public void showPath(int to){
        List<Edge> edgeList = shortestPath(to);
        StringBuilder sb = new StringBuilder();
        for (Edge edge : edgeList){
            sb.append(edge.from).append(" -> ").append(edge.to).append("\n");
        }
        System.out.println(sb.toString());
    }
}
